#pragma warning(disable : 4996)
#include"heap.h"
void InIt(Heap* hp)
{
	hp->capicity = 4;
	hp->size = 0;
	HPDateType* tail = (HPDateType*)malloc(sizeof(HPDateType) * hp->capicity);
	if (tail == NULL)
	{
		perror("malloc fail");
	}
	hp->tree = tail;
}

void HeapDestory(Heap* hp)
{
	free(hp->tree);
	hp->tree = NULL;
	hp->capicity = 0;
	hp->size = 0;

}

void Expansion(Heap*hp)
{
	HPDateType* tail = (HPDateType*)realloc(hp->tree,sizeof(HPDateType) * hp->capicity * 2);
	if (tail == NULL)
	{
		perror("relloc fail");
	}
	hp->tree = tail;
	hp->capicity *= 2;
}

void Swap(HPDateType* tree, HPDateType parents, HPDateType children)
{
	HPDateType temp = tree[children];
	tree[children] = tree[parents];
	tree[parents] = temp;
}

void AdjustUp(HPDateType* tree, int children)
{
	int parents = (children - 1) / 2;
	while(children!=0)
	{
		if (tree[children] < tree[parents])
		{
			Swap(tree, parents, children);
			children = parents;
			parents = (children - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

void HeapPush(Heap* hp, HPDateType x)
{
	if (hp->size == hp->capicity)
	{
		Expansion(hp);
	}
	hp->tree[hp->size] = x;
	AdjustUp(hp->tree, hp->size);
	hp->size++;

}

void AdjustDown(HPDateType* tree, int parents,int size)
{
	HPDateType  leftchildren;
	HPDateType  max;
	leftchildren = parents * 2 + 1;
	max = leftchildren;

	while (leftchildren < size)
	{
		if (leftchildren + 1 < size && tree[leftchildren + 1] > tree[leftchildren])
		{
			max = leftchildren + 1;
		}

		if (tree[parents] < tree[max])
		{
			Swap(tree, parents, max);
			parents = max;
			leftchildren = parents * 2 + 1;
			max = leftchildren;
		}
		else
		{
			break;
		}
	}
}

void HeapPop(Heap* hp)
{
	assert(hp->tree != NULL);
	assert(hp->size > 0);
	Swap(hp->tree, 0, hp->size - 1);
	AdjustDown(hp->tree, 0, hp->size - 1);
	hp->size--;
}

HPDateType HeapTop(Heap* hp)
{
	assert(hp->size != 0);
	return hp->tree[0];

}

int HeapSize(Heap* hp)
{
	return hp->size;
}

bool HeapEmpty(Heap* hp)
{
	return (hp->size == 0 ? true : false);
}